package study;

import java.util.Arrays;
import java.util.PriorityQueue;

public class MaxSlidingWindow {

    public static int[] maxSlidingWindow(int[] num, int k) {
        PriorityQueue<Integer> list = new PriorityQueue<>((input1, input2) -> input2 - input1);
        for (int i = 0; i < k; i++) {
            list.offer(num[i]);
        }
        int[] ret = new int[num.length - k + 1];
        ret[0] = list.peek();
        for (int i = k; i < num.length; i++) {
            list.clear();
            for (int j = 0; j < k; j++) {
                list.offer(num[i - k + 1 + j]);
            }
            ret[i - k + 1] = list.peek();
        }

        return ret;
    }

    // 对拍
    public static int[] maxSlidingWindow2(int[] num, int k) {
        int[] ret = new int[num.length - k + 1];
        for (int i = 0; i < num.length - k + 1; i++) {
            int max = 0;
            for (int j = 0; j < k; j++) {
                if (num[i + j] > max) {
                    max = num[i + j];
                }
            }
            ret[i] = max;
        }
        return ret;
    }

    public static void main(String[] args) {
        int[] input = {1, 3, -1, -3, 5, 3, 6, 7};
        int k = 3;
        int[] ret1 = maxSlidingWindow(input, k);
        int[] ret2 = maxSlidingWindow2(input, k);
        System.out.println(Arrays.toString(ret1));
        System.out.println(Arrays.toString(ret2));
    }
}
